package practise.leetcode.q120;

import java.util.List;

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle.isEmpty()) {
            return 0;
        }

        int rows = triangle.size();
        int cols = triangle.get(rows - 1).size();

        int[][] dp = new int[rows][cols];

        dp[0][0] = triangle.get(0).get(0);
        for (int row = 1; row < rows; row++) {
            dp[row][0] = dp[row -1][0] + triangle.get(row).get(0);
        }

        for (int row = 1; row < rows; row++) {
            List<Integer> rowNums = triangle.get(row);
            for (int col = 1; col < rowNums.size(); col++) {
                if (col == rowNums.size() - 1) {
                    dp[row][col] = dp[row -1][col - 1] + rowNums.get(col);
                    continue;
                }
                dp[row][col] = Math.min(dp[row -1][col - 1], dp[row - 1][col]) + rowNums.get(col);
            }
        }

        int min = dp[rows  - 1][0];
        for (int col = 1; col < cols; col++) {
            if (dp[rows - 1][col] < min) {
                min = dp[rows - 1][col];
            }
        }

        return min;
    }
}
